#include <stdlib.h>
#include <stdio.h>

typedef int ElemType;
typedef struct _Node{
    ElemType data;
    struct _Node *next;
}Node, *QueuePtr;

typedef struct{
    QueuePtr front; //队头
    QueuePtr rear;  //队尾
}LinkedQueue;

void init(LinkedQueue &Q){
    Q.front = Q.rear = (QueuePtr) malloc(sizeof(Node));
    if(!Q.front){
        exit(0);
    }
    Q.front->next = NULL;
}

void DestoryQueue(LinkedQueue &Q){
    
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
}

void EnQueue(LinkedQueue &Q, ElemType e){
    QueuePtr p = (QueuePtr) malloc(sizeof(Node));
    if(!p){
        exit(0);
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}

void DeQueue(LinkedQueue &Q, ElemType &e){
    if(Q.front == Q.rear){//空队
        return;
    }

    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(p == Q.rear){    //如果删除的是队列中最后一个，队尾就没有了
        Q.rear = Q.front;//需要重新赋值
    }
    free(p);
}